package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/6/11 21:50
 */
// Medium
public class RemoveNthFromEnd_19 {


    /**
     * 通过快慢指针实现了距离的固化，通过设置两个节点的固定距离，实现了对于倒数节点的寻找
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        // 头结点会发生变化，因此用一个dummy结点，令其固定指向头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = head, fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 说明删除头结点
        if (fast == null) {
            dummy.next = head.next;
        } else {
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
        }
        return dummy.next;
    }

    static class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head == null) return null;

            ListNode fast = head, slow = null;
            while (n-- > 0) {
                fast = fast.next;
            }

            while (fast != null) {
                slow = slow == null ? head : slow.next;
                fast = fast.next;
            }

            if (slow == null) {
                return head.next;
            } else {
                slow.next = slow.next.next;
                return head;
            }
        }
    }

}
